1. Field of the Invention
Embodiments of the present invention generally relate to the field of network configuration and, more particularly, to recovery from a failed link configured with the Spanning Tree Protocol (STP).
2. Description of the Related Art
Larger local area networks (LANs) comprise multiple sections, where each section may be used by a particular workgroup or department. These LANs may be divided in this manner for security purposes and to improve traffic flow by filtering out data packets that are not destined for a particular section. Called network segments, these sections may be separated from the rest of the LAN by a network bridge, sometimes called a network switch in marketing literature.
A single network bridge is typically a computer with multiple ports used to connect multiple network segments together. The bridging function includes receiving data from a port and transferring that data to other ports for receipt by other network entities. Network bridges operate along the data link layer, also known as layer 2 in the Open System Interconnection (OSI) Reference Model. Since bridging decisions are based solely on end-station MAC addresses, which are contained within the data frame, network bridges are able to move such data frames rapidly from one port to another.
Interconnecting all of the network bridges could be as simple as daisy-chaining one bridge to the next in series, but sound network design typically advocates providing redundant links to offer an alternative path should a link fail. However, if a network had more than one path to a destination activated, then this might create a loop, and the network bridges could endlessly broadcast data frames. This situation is called a broadcast storm, and it can cripple a network. In addition, network bridge loops can cause the bridges to misinterpret results.
To prevent loops in bridged networks, the Spanning Tree Protocol (STP) according to IEEE 802.1D is often used. The structure of STP corresponds to that of the spanning tree in graph theory where a connected, undirected graph has a subgraph akin to a tree spanning the entire graph and connecting all of the vertices together. Several different spanning trees can be associated with a single graph. Since a weight can be assigned to each edge of a graph and a spanning tree can be assigned a weight equal to the sum of the weights of the edges within this spanning tree, a minimum spanning tree can be determined which possesses a weight less than or equal to the weight of every other spanning tree for that particular graph. In bridged networks, the minimum spanning tree algorithm dynamically determines the best path from source to destination and ensures that only one path is active at any one time by detecting loops and blocking network bridge ports as required.
A root exists at the base of every tree, and following the guidelines of STP, the spanning tree is no different. The spanning tree algorithm automatically selects a root bridge according to a set of rules that ensure only a single bridge is elected as the root bridge for a given network. Each bridge has a media access control (MAC) address and a configurable priority number, which compose the bridge identification (BID). The root bridge is elected based on the lowest (the best) priority number using the BID. If a tie occurs, then the MAC address is used to break the tie with the bridge with the lowest MAC address out of the group with the lowest priority number prevailing. Since no two MAC addresses are the same, one network bridge will always be successfully selected as the root bridge. Other bridges can subsequently calculate the shortest distance to the root bridge using bandwidth as a weighting metric and so produce a loop free topology. Even though the priority number is normally left at its default value, it can be reconfigured to a lower number if the network administrator wants to force a particular bridge to be elected as the root bridge. Otherwise, the entire process is completely automated.
To aid in this process and enable communication between the network bridges, BIDs and other STP information are carried in special data frames called bridge protocol data units (BPDUs). Regularly exchanged at 2 second intervals, BPDUs allow bridges to keep track of network changes and activate or disable ports as required. When a new device is first connected to a bridge port, the port will not immediately start to forward data. Instead, the port will run through a number of states while it processes BPDUs and determines the topology of the network. When this device is a host (e.g. client computer, printer, or server), the port will always go into forwarding mode—the normal operating mode where the port is receiving and sending data—although after a delay of about 30 seconds while the port goes through the listening and learning modes. Of course, if the new device connected to the port is another bridge, the port may remain in blocking mode if activating the port would cause a loop in the network.
Since a delay of 50 seconds is unacceptable by conventional standards, Rapid Scanning Tree Protocol (RSTP) was developed as an evolution of STP and was standardized by IEEE 802.1w. RSTP provides for faster spanning tree convergence after a topology change, allowing a bridge port to enter forwarding mode immediately upon the attachment of an end device. Since the 2004 edition of IEEE 802.1d, STP has been superseded by RSTP. In RSTP, there are only three port states: discarding, learning and forwarding. STP's disabled, blocking, and listening states have been combined into RSTP's discarding state. Also according to RSTP, the port role is now a variable assigned to a given port with STP's blocking port role being split into backup and alternate port roles and leaving the root and designated ports. The spanning tree algorithm determines the role of a port based on BPDUs as described above and further explained below.
Considering a simple network with only three network bridges labeled A, B, and R as shown in FIG. 1a, only two links 102, 104 are required to connect all the bridges together. A third link 106 may be provided for redundancy in case of a link failure, but one of the ports should be blocked to prevent a loop topology according to STP/RSTP. A root bridge 108 is selected based on sending the lowest priority number BPDUs, lower (better) than any other bridge can send. For a particular bridge, the port that is closest to the root bridge in terms of path cost (i.e. receives the best BPDU) is designated as a root port.
Two root ports 110 are shown in FIG. 1b. The root bridge 108 is the only bridge in the network that does not have a root port. Regarding FIG. 1c, a port assumes a designated port role if it can send the best BPDU on the network segment to which it is connected. For a given segment, there can only be one path toward the root bridge 108. If there were two, a loop would exist, which is undesirable, as described above.
All bridges connected to a given segment listen to each other's BPDUs and agree on the bridge sending the best BPDU as the designated bridge for the segment. The corresponding port on the designated bridge is a designated port 112. In order to leave the third link 106 connected in the network in case of a link failure in the other two links 102, 104, one of the ports of bridge A or bridge B must be blocked. A blocked port receives a better priority number BPDU than the one it would send out on its segment.
When the ends of a network segment reside on different bridges, as shown in FIG. 1d, the blocked port is termed an alternate port 114. When the two ends reside on the same bridge, the blocked port is called a backup port (not shown). Note that the port on the other end of a segment with an alternate port 114 becomes a designated port 112.
In the event of a link failure between any of the bridges, the network may be reconfigured such that a blocked port may be enabled, thereby allowing the use of alternate paths. While a very simple network of three bridges is shown in FIGS. 1a-1d, much larger networks in a ring topology are commonplace. In such networks, in the event of an indirect link failure (a failure that is not detected by a bridge hosting an alternate port), substantial time may be required because the spanning tree would have to rediscover the topology before restoring the connectivity.
Accordingly, what is needed is a method to speed recovery in the event of a link failure, for example, in an effort to achieve a fast reconvergence time with minimal impact on network performance.